The invention relates to a method for checking an integrated electrical circuit, which is in the form of a layout on a computer system, for faults caused by the manufacturing process or by the configuration of the integrated electrical circuit.
Checks such as these frequently make use of methods in which integrated electrical circuits are checked using proprietary manufacturer-specific design rule check rules or DRC rules. Furthermore, methods are feasible, in particular, test programs for detecting high-impedance circuit elements that cause faults and are connected to a number of circuit networks. These methods check the integrated electrical circuits for faulty circuit elements on a computer system by inserting xe2x80x9csoft connects.xe2x80x9d
Methods such as these for checking integrated electrical circuits are dependent on the availability of a description that is as realistic as possible of the integrated electrical circuit to be checked, on a memory unit in a computer system, with this description being created such that conventional test procedures can be applied to the description.
Integrated electrical circuits are subdivided into a large number of electrical circuit networks that are connected to one another. The characteristics of these circuit networks are frequently stored in the form of polygon data structures in order to create a layout of the integrated electrical circuit, with these polygon data structures using polygons to represent the circuit configurations contained in the respective circuit network.
In such a case, a separate polygon data structure is produced for each circuit network, with information from a number of circuit networks, which match electrically and geometrically, in each case being combined to form a polygon data structure. In reality, integrated electrical circuits often contain different electrical circuit networks, which have the same electrical characteristics, or electrical characteristics that are very similar to one another, but in which the geometry of the circuit elements that they contain differs. Separate polygon data structures are frequently produced in each case for circuit networks such as these when creating a description of an integrated electrical circuit on a computer system.
When producing a large number of polygon data structures that are very similar to one another, one problem that arises is that a very large memory area is required to describe the basic integrated electrical circuit on a memory unit of a computer system. A further disadvantage in this case is that the formation of the data structure of the circuit description from the individual polygon data structures is highly time-consuming. Furthermore, the memory requirement and the time required for use of the test procedures described above for a circuit description such as this are very extensive. These disadvantages become even more important as the integrated electric circuits on which they are based becomes more extensive and more complex.
It is accordingly an object of the invention to provide a method for checking an integrated electrical circuit that overcomes the hereinafore-mentioned disadvantages of the heretofore-known devices and methods of this general type and that can be used to create an improved description of an integrated electrical circuit. The integrated electrical circuit is intended to be capable of being checked for faults quickly and reliably, using this description.
With the foregoing and other objects in view, there is provided, in accordance with the invention, a method for checking an integrated electrical circuit to be described by a layout including circuit network descriptions of the integrated electrical circuit, each of the circuit network descriptions being in a form of one of a file and a part of a file on a memory unit of a computer system and each of the circuit network descriptions having at least one polygon each representing one circuit element of the integrated electrical circuit and information regarding electrical characteristics of circuit elements of the integrated electrical circuit, the layout having instantiations of at least one circuit network description and information about a geometrical shape and a configuration of the instantiations with respect to one another, the layout being described by a raw data structure associating each instantiation of a circuit network description with only one polygon data structure, includes the step of carrying out with a computer program the steps of (a) selecting a circuit network description from the layout, (b) determining the instantiations of the circuit network description in the layout, (c) determining the respectively geometrically identical and geometrically different instantiations of the circuit network descriptions by analyzing polygon data structures, (d) forming variants for the instantiations of the circuit network descriptions and assigning the instantiations to these variants, geometrically different instantiations being combined into respectively different variants and geometrically matching instantiations being combined into respectively identical variants, (e) forming a new data structure associating the circuit network description with only one polygon data structure, geometrical differences between the instantiations of the same circuit network description being taken into account by variants in the polygon data structure, (f) storing the formed new data structure as one of a file and a part of a file on the memory unit of the computer system, and (g) checking the layout of the integrated electrical circuit using the new data structure stored in step f) for faults caused by a configuration of the integrated electrical circuit.
With the objects of the invention in view, there is also provided a method for checking an integrated electrical circuit to be described by a layout including circuit network descriptions of the integrated electrical circuit, each of the circuit network descriptions being in a form of one of a file and a part of a file on a memory unit of a computer system and each of the circuit network descriptions having at least one polygon each representing one circuit element of the integrated electrical circuit and information regarding electrical characteristics of circuit elements of the integrated electrical circuit, the layout having instantiations of at least one circuit network description and information about a geometrical shape and a configuration of the instantiations with respect to one another, the layout being extending over a number of levels disposed one above another, the layout being described by a raw data structure associating each instantiation of a circuit network description with only one polygon data structure, includes the step of carrying out with a computer program the steps of (a) selecting a circuit network description from the layout, (b1) selecting a highest level from the layout, (b2) determining the instantiations of the selected circuit network description on the level selected in step b1), (b3) forming difference polygons by comparing the instantiations on the level selected in step b1) in pairs, (b4) forming variants for instantiations having different difference polygons, (b5) checking the difference polygons acting on circuit network descriptions in a next-lower level, (b6) assigning the instantiations to the variants formed in step b4) based upon the difference polygons, (c1) selecting the next-lower level, (c2) determining the instantiations of the selected circuit network description on the level selected in step c1), (c3) forming difference polygons by comparing the instantiations on the level selected in step c1) in pairs, (c4) combining the difference polygons formed in step c3) with the previously formed difference polygons, (c5) checking the difference polygons acting on circuit network descriptions in a next-lower level, (c6) assigning the instantiations to the variants already having been formed based upon the difference polygons, (c7) forming further variants for instantiations having difference polygons differing from the difference polygons combined in step c4), (c8) assigning the instantiations found in step c7) to the variants formed in step c7), (d1) repeating steps b1) to b5), c1) and c8) in a loop until a lowest level in the layout has been reached, (e) forming a new data structure associating the circuit network description with only one polygon data structure, geometrical differences between the instantiations of the same circuit network description being taken into account by variants in the polygon data structure, (f) storing the formed new data structure as one of a file and a part of a file on the memory unit of the computer system, and (g) checking the layout of the integrated electrical circuit using the new data structure stored in step f) for faults caused by a configuration of the integrated electrical circuit.
With the objects of the invention in view, there is also provided a method for checking an integrated electrical circuit having circuit elements with electrical characteristics, including the steps of providing a layout describing the integrated electrical circuit, the layout having circuit network descriptions of the integrated electrical circuit, each of the circuit network descriptions being in the form of one of a file and a part of a file on a memory unit of a computer system, having at least one polygon each representing one of the circuit elements, and having information about the electrical characteristics of the circuit elements, having at least one of a plurality of instantiations of at least one circuit network description, the instantiations having a geometrical shape and a configuration, having information about the geometrical shape and the configuration of the instantiations with respect to one another, and being described by a raw data structure associating each instantiation of a circuit network description with only one of a plurality of polygon data structures, and carrying out the following steps with a computer program: (a) selecting a circuit network description from the layout; (b) determining the instantiations of the circuit network description in the layout; (c) determining the respectively geometrically identical and geometrically different instantiations of the circuit network descriptions by analyzing the polygon data structures; (d) forming variants for the instantiations of the circuit network descriptions and assigning the instantiations to the variants, geometrically different ones of the instantiations being combined into respectively different variants and geometrically matching ones of the instantiations being combined into respectively identical variants; (e) forming a new data structure associating the circuit network description with only one polygon data structure, geometrical differences between the instantiations of the same circuit network description being taken into account by variants in the polygon data structure; (f) storing the formed new data structure as one of a file and a part of a file on the memory unit of the computer system; and (g) checking the layout of the integrated electrical circuit using the new data structure stored in step f) for faults caused by a configuration of the integrated electrical circuit.
With the objects of the invention in view, there is also provided a method for checking an integrated electrical circuit having circuit elements with electrical characteristics, including the steps of providing a layout describing the integrated electrical circuit, the layout having circuit network descriptions of the integrated electrical circuit, each of the circuit network descriptions being in the form of one of a file and a part of a file on a memory unit of a computer system, having at least one polygon each representing one of the circuit elements, and having information about the electrical characteristics of the circuit elements, having at least one of a plurality of instantiations of at least one circuit network description, the instantiations having a geometrical shape and a configuration, having information about the geometrical shape and the configuration of the instantiations with respect to one another, extending over a number of levels disposed one above another, and being described by a raw data structure associating each instantiation of a circuit network description with only one of a plurality of polygon data structures, and carrying out the following steps with a computer program: (a) selecting a circuit network description from the layout; (b1) selecting a highest level from the layout; (b2) determining the instantiations of the selected circuit network description on the level selected in step b1); (b3) forming difference polygons by comparing the instantiations on the level selected in step b1) in pairs; (b4) forming variants for instantiations having different difference polygons; (b5) checking the difference polygons acting on circuit network descriptions in a next-lower level; (b6) assigning the instantiations to the variants formed in step b4) based upon the difference polygons; (c1) selecting the next-lower level; (c2) determining the instantiations of the selected circuit network description on the level selected in step c1); (c3) forming difference polygons by comparing the instantiations on the level selected in step c1) in pairs; (c4) combining the difference polygons formed in step c3) with the previously formed difference polygons; (c5) checking the difference polygons acting on circuit network descriptions in a next-lower level; (c6) assigning the instantiations to the variants already having been formed based upon the difference polygons; (c7) forming further variants for instantiations having difference polygons differing from the difference polygons combined in step c4); (c8) assigning the instantiations found in step c7) to the variants formed in step c7); (d1) repeating steps b1) to b5), c1) and c8) in a loop until a lowest level in the layout has been reached; (e) forming a new data structure associating the circuit network description with only one polygon data structure, geometrical differences between the instantiations of the same circuit network description being taken into account by variants in the polygon data structure; (f) storing the formed new data structure as one of a file and a part of a file on the memory unit of the computer system; and (g) checking the layout of the integrated electrical circuit using the new data structure stored in step f) for faults caused by a configuration of the integrated electrical circuit.
In accordance with another mode of the invention, following step d) or d1), steps a) to d) or d1), respectively, are repeated in a loop for further circuit network descriptions in the layout.
According to the invention, an integrated electrical circuit has one or more circuit networks, each having a large number of circuit elements. An integrated electrical circuit typically extends over a number of levels, by virtue of the way in which it is produced, in which case, circuit networks can extend over one or more levels. The circuit elements are defined by shape and characteristic information. A complete integrated electrical circuit is characterized by the circuit elements contained in it and by the information about their absolute and/or about their relative positions with respect to one another.
According to the invention, a description of an integrated electrical circuit is produced in the form of a layout on a computer system, in particular, on a screen or on an output unit such as a printer. The layout in this case includes descriptions of one or more circuit networks of the integrated electrical circuit under consideration, which are each stored in a file or in each case in a part of a file on a memory unit of the computer system. Each circuit network is in this case described by at least one polygon, with the polygons each representing one circuit element of the integrated electrical circuit. Each polygon is in this case associated with information about the electrical characteristics of the circuit elements.
The layout of the integrated electrical circuit, which may extend over a number of levels, is composed of at least one circuit network description as described above, and of information about the geometrical shape and the configuration of these circuit network descriptions with respect to one another. The individual circuit network descriptions are stored in separate files. Accordingly, one speaks of the circuit network descriptions being instantiated or inserted into the layout. If one layout contains the same circuit network more than once, then one speaks of the relevant layout containing a number of instantiations of one circuit network description.
According to the present invention, the layout is described by a raw data structure, which associates each instantiation of a circuit network description with one, and only one, separate polygon data structure. The polygon data structures in this case contain information about the electrical characteristics of the polygons that they contain, as well as connection information for these polygons. The raw data structure, furthermore, contains the linking information for the individual polygon data structures.
In a first step according to the invention, a description of a circuit network is selected from a layout on an integrated electrical circuit. In this case, the method according to the invention is applied to an extraction process. An extraction process means the determination and hierarchical storage of the circuit networks and components. In this case, the raw data structure is produced from the extraction. In addition to the determined circuit networks, the result of the extraction process also provides information about the geometrical shape and configuration of the instantiations of the circuit networks with respect to one another.
In the second method step, all the instantiations of the selected circuit network description in this layout are determined. If the layout extends over a number of levels, then a top-down approach is, preferably, used in this case, covering the levels in the layout hierarchically.
In the next step, these instantiations are checked for matches and differences, with the polygon data structures being analyzed. Variants are, then, formed for the instantiations of the circuit network description. Geometrically different instantiations are assigned to respectively different variants, and geometrically matching instantiations are assigned to respectively identical variants. The number of variants that are formed in the process is kept to a minimum.
The next step according to the invention provides for a new data structure to be formed, which associates each circuit network description with one, and only one, polygon data structure. The geometrical differences between instantiations in the same circuit network description are taken into account by the variants that were formed in the previous step and that are linked to the polygon data structure. The data structure so produced is stored as a file or as a part of a file on the memory unit of the computer system.
The layout of the integrated electrical circuit is now investigated, using the data structure so modified, for faults that have been caused by the configuration of the integrated electrical circuit or by the sequence of the production steps for manufacturing the integrated electrical circuit. The methods that are used in this case for checking, including design rule check rules as well as test procedures that operate with the insertion of soft connects, are known to those skilled in the art and do not need to be explained any further at this point.
One fundamental idea of the invention is for all the instantiations of the same circuit network description to be applied to one, and only one, polygon data structure. Instantiations are combined in a polygon data structure such as this, which, although they have electrically matching or very similar characteristics, have different geometries to one another, however. The geometrical differences between the electrically matching instantiations are taken into account by variants, which are associated with the polygon data structure that is formed. These variants contain only the delta information for the respective instantiations. This means that the complete information content of a polygon data structure is not applied for each variant and, instead of this, only the differences from the referenced polygon data structure are defined for each variant.
According to a further fundamental idea of the invention, an algorithm is provided for variant generation, which forms the polygon data structures based upon the electrical characteristics of the circuit elements that are represented by polygons, and forms the variants based upon the geometrical differences between the instantiations of circuit network descriptions that are in each case referenced by the same polygon data structure. This results in an exact geometric representation of the polygons being formed from a logical representation.
The data structure that is produced and stored using the method according to the invention occupies very little memory space in comparison to prior art data structures, and has a very compact memory form. The number of polygons to be stored is reduced considerably in comparison to the prior art methods.
The hierarchical level of the data structure that is created is far higher than in the case of the prior art methods, which leads to quicker formation of the data structure and to quicker processing, which is more efficient of memory, of the programs, in particular, test programs, which work on this data structure.
Furthermore, the method according to the invention can result in the production of an xe2x80x9cas if flatxe2x80x9d representation of circuit networks for the subsequent applications.
Particularly extensive and complex integrated electrical circuits that, until now, it has not been possible to check, or which it has been possible to check only to a limited extent, for faults caused by the configuration or the production process of the integrated electrical circuit can, now, advantageously be checked with computer assistance.
According to one embodiment of the invention, the layout of an integrated electrical circuit extends over a number of levels that are disposed one above the other. These levels correspond to the production-engineering levels of the integrated electrical circuit. The polygons and circuit network descriptions that are present on the levels of the layout correspond to the circuit elements and circuit networks that are present on the respective levels of the integrated electrical circuit.
In this embodiment of the invention, the situation is considered in which instantiations of circuit networks that electrically match or are very similar but that differ geometrically occur on different levels in a layout. A hierarchically constructed master network, which can be formed from a network list, is used in this case, which represents the logical configuration of the basic integrated electrical circuit.
In this embodiment of the method according to the invention, the following steps are carried out instead of the steps of determination of the instantiations of the circuit network description, determination of the geometrically identical instantiations and of the geometrically different instantiations, the formation of variants for these instantiations and the assignment of the instantiations to these variants.
First of all, the highest level in the layout is determined and is selected. The instantiations of the selected circuit network description on this level are determined and difference polygons are formed by comparing these instantiations in pairs, with these difference polygons representing the differences between the instantiations. Variants are, then, formed for instantiations that have different difference polygons. This is followed by a check to determine whether or not these difference polygons are connected to circuit network descriptions in the next-lower level in the layout. The instantiations in the selected level of the layout are, then, assigned to these variants based upon their difference polygons.
The next step in the method according to the invention includes the selection of the next-lower level in the layout. The instantiations of the selected circuit network description are determined on this level, and the difference polygons are formed by comparing the instantiations on this level in pairs. The difference polygons so formed are combined with the previously formed difference polygons. Once the difference polygons that act on circuit network descriptions in the next-lower level have been checked, the instantiations are assigned to the already formed variants based upon their difference polygons.
In the next step of the method according to the invention, further variants are formed for instantiations of the circuit network description whose difference polygons do not match the already formed difference polygons. Those instantiations that have such different difference polygons are assigned to the newly formed variants.
The next step in the method according to the invention provides for these steps to be repeated in the form of a loop. The end of the method according to the invention is reached when the lowest level in the layout has been processed in the final run through the loop.
This embodiment of the invention is based on the idea of the layout being processed hierarchically in levels. The above description started from the hierarchically highest level of the layout and was processed successively level by level until the lowermost level in the layout was reached. This is also referred to as a xe2x80x9ctop downxe2x80x9d approach. A reverse procedure from the lowermost to the uppermost level is, likewise, feasible, that is to say, a xe2x80x9cbottom upxe2x80x9d approach. This algorithm according to the invention for variant generation is very effective and very fast.
The hierarchy level that can be achieved can be set to very high by the embodiment of the invention. Circuit network descriptions that match electrically but that differ geometrically can, thus, be stored in a reliable manner that uses memory particularly optimally. The data structure that is produced is particularly suitable for subsequent applications, in particular, test procedures.
It is particularly advantageous for the method according to the invention to be carried out successively for two or more circuit network descriptions, in particular, for all the circuit network descriptions in the layout under consideration, in the form of a loop. This makes it possible to form a complete data structure, which uses the memory in a particularly optimum manner.
The invention also applies to a computer program for carrying out a method for checking an integrated electrical circuit. The computer program is in such a case configured such that a method according to the invention can be carried out once a layout or a part of a layout has been entered or selected. In this case, the method results in a modified data structure that uses memory in an optimal manner, and that can be used for subsequent applications, in particular, for test programs.
In accordance with a further mode of the invention, the method according to the invention is executed on a computer.
The computer program according to the invention results in a simple data structure that uses memory in an optimum manner and that allows improved checking of integrated electrical circuits as well as improving the delay time in comparison to the known data structures.
The invention also relates to a computer program that is contained on a memory medium that is stored in a computer memory, which is contained in a direct access memory or which is transmitted on an electrical carrier signal.
In accordance with an added mode of the invention, there is provided a computer-readable medium having computer-executable instructions for performing the method according to the invention.
The invention also relates to a data storage medium having such a computer program and to a method in which a computer program such as this is downloaded from an electronic data network, such as the Internet, to a computer that is connected to the data network. The method according to the invention is implemented in the xe2x80x9cHERCxe2x80x9d computer program.
In accordance with an additional mode of the invention, there is provided a storage medium having computer-executable instructions for performing the method according to the invention.
In accordance with yet another mode of the invention, there is provided a computer memory having computer-executable instructions for performing the method according to the invention.
The computer memory can be a random access memory or a direct access memory.
In accordance with yet a further mode of the invention, there is provided an electrical carrier signal carrying computer-executable instructions for performing the method according to the invention.
In accordance with yet an added mode of the invention, there is provided a data carrier having computer-executable instructions for performing the method according to the invention.
In accordance with yet an additional mode of the invention, there is provided a method for downloading a computer program for checking an integrated electrical circuit, including the steps of providing an electronic data network and downloading the computer program according to the invention from the electronic data network to the computer.
In accordance with a concomitant mode of the invention, the electronic data network is the Internet and the computer is connected to the Internet.
In summary, an algorithm such as this for variant generation can be configured as follows. The algorithm operates using record fields in which the data such as instantiations, variants, and polygons is stored. The recursive formation of components and the collection of the results are carried out xe2x80x9cbottom up.xe2x80x9d As a side effect, the number of instantiations for each variant is counted. The components are in this case formed by first processing the polygons with a graph search and, then, by processing the search networks using a union find technique. The variant formation, the allocation of the numbers for the instantiations for each variant, the graph search of the polygons, and the connections through the cell levels and through the network descriptions are carried out by separate functions. Once the data has been determined, it is evaluated. The results are collected in xe2x80x9cabstract records,xe2x80x9d which are not stored until the start of the evaluation phase. The recursion process that is used for variant formation is, preferably, carried out indirectly.
Other features that are considered as characteristic for the invention are set forth in the appended claims.
Although the invention is illustrated and described herein as embodied in a method for checking an integrated electrical circuit it is, nevertheless, not intended to be limited to the details shown because various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.
The construction and method of operation of the invention, however, together with additional objects and advantages thereof, will be best understood from the following description of specific embodiments when read in connection with the accompanying drawings.